#leetcode题目81：搜索旋转排序数组II
#难度：中等

#方法：二分查找

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        while len(nums) > 1 and nums[0] == nums[-1]:
            nums.pop()
        i, j = 0, len(nums) - 1
        while i <= j:
            mid = i + (j - i) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] <= nums[j]:
                if target > nums[mid] and target <= nums[j]:
                    i = mid + 1
                else:
                    j = mid - 1
            else:
                if target >= nums[i] and target < nums[mid]:
                    j = mid - 1
                else:
                    i = mid + 1
        return False



#测试数据
nums=[2,5,6,0,0,1,2]
target=0
#预期输出：True
solution=Solution()
print(solution.search(nums,target))

nums=[2,5,6,0,0,1,2]
target=3
#预期输出：False
solution=Solution()
print(solution.search(nums,target))